// 计数质数

package Leetcode;

import java.util.Arrays;

class Solution204_1 {
    public int countPrimes(int n) {
        if (n == 0 || n == 1 || n == 2)
            return 0;
        if (n == 3)
            return 1;
        int count = 2;
        a: for (int i = 4; i < n; i++) {
            int j;
            for (j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0)
                    continue a;
            }
            count++;
        }
        return count;
    }
}

class Solution204_2 {
    public int countPrimes(int n) {
        // 1表示质数，0表示合数
        int[] isPrime = new int[n];
        Arrays.fill(isPrime, 1);
        int count = 0;
        for (int i = 2; i < n; i++) {
            // 如果为质数则其倍数为合数
            if (isPrime[i] == 1) {
                count++;
                if ((long) i * i < n) { //判断是否超过数据类型
                    for (int j = i * i; j < n; j = j + i)
                        isPrime[j] = 0;
                }
            }
        }
        return count;
    }

    // public int isPrime(int n) {
    // // 返回1表示质数，返回0表示合数
    // if (n == 2 || n == 3)
    // return 1;
    // for (int i = 2; i < Math.sqrt(n); i++) {
    // if (n % i == 0)
    // return 0;
    // }
    // return 1;
    // }
}